There are many situations where items need to be allocated among two or more parties. Often, the items are related, so that a party's value for a package of items is different from the sum of the party's values for the separate items. Auctions (or auction-like processes) are often used to allocate items among two or more parties, but the design of an efficient auction is a technically difficult problem when the items are related.
When items are related, they are often related so as to be complements or substitutes. Two items are said to be complements when they are used together; more precisely, items A and B are complements when reducing the price of item A causes the demand for item B to increase. Two items are said to be substitutes when one is used in place of the other; more precisely, items A and B are substitutes when reducing the price of item A causes the demand for item B to fall.
One example of allocating complementary items may be the case of allocating licenses for telecommunications spectrum. A government may offer a variety of spectrum licenses, each covering a specified bandwidth in a specified geographic area. A wireless telephone company seeking spectrum rights may find that it requires a minimum of 20 MHz of bandwidth in a given geographic area, in order to be able to provide a useful service. Thus, two 10 MHz licenses covering the same geographic area may be complements. At the same time, a wireless telephone company may realize synergies from serving two geographically adjacent markets, so licenses for two adjacent markets may also be complements.
One example of allocating substitute items may be the case of allocating financial instruments. A government may offer three-month, six-month, one-year, two-year and five-year debt securities. For a buyer of government securities, these different durations are likely to be substitutes to at least a certain extent, since they each provide a safe investment opportunity for the next three months. For the government, too, these different durations are likely to be substitutes to at least a certain extent, since they each provide a vehicle for financing the government's debt for the next three months.
In some of the most difficult situations some items are complements and other items are substitutes within the same allocation problem. For example, consider the case of allocating capacity at one or more capacity-onstrained airport. The airport authority may offer a variety of landing slots and takeoff slots at different times of the day. Various slots may be complementary goods: for example, an airline is likely to desire a takeoff slot about one hour after each landing slot, and an airline may desire several takeoff and landing slots bunched together in order to be able to maintain a “hub-and-spoke” operation. Also, various slots may be substitute goods: for example, an airline may be able to use a 10:00 am landing slot in place of a 9:00 am landing slot, although the former slot may not be anywhere as valuable as the latter slot. The slots at two airports serving the same city are likely to be substitutes for one another, while the slots at two ends of a heavily trafficked route are likely to be complementary goods.
In the last few years, there has been growing interest in auction processes that allow bidders much greater freedom to name the packages on which they bid during the auction. Such auctions, which may determine the packaging, pricing and allocation decisions, can be called “package auctions,” “combinatorial auctions,” or “auctions with package bidding.” Typically, bidders in these auctions describe the packages that they wish to acquire and make bids for the named packages.
One especially promising version of a package auction is a clock auction. It is an iterative auction process in which the auctioneer announces prices, bidders respond with quantities, the prices are adjusted according to the relation between the quantities bid and the quantities being auctioned, and the process is allowed to repeat. Such auction processes are particularly effective in allocating multiple units of multiple types of goods. (For a longer discussion, see “System and Method for an Auction of Multiple Types of Items,” International Patent Application No. US02/16937.)
A second especially promising version of a package auction is aproxy auction. It is effectively a sealed-bid auction. The bidder inputs valuation information into a proxy agent, so that the proxy agent possesses information concerning the valuation of some or all of the possible packages. The proxy agent then submits package bids on behalf of the bidder, selecting one or more packages that optimize the difference between the bidder's value and the amount that can be bid for the package. The auctioneer then selects provisionally-winning bids by solving the optimization problem of selecting bids, at most one from each bidder, that optimize revenues subject to a feasibility constraint. Proxy agents for bidders who are not selected as provisional winners then submit new bids, and the process continues until the bidders who are not provisional winners have no profitable bids remaining to be placed. (For a longer discussion, see “System and Method for a Dynamic Auction with Package Bidding,” International Patent Application No. US01/43838.)